package main

import "fmt"

/**
 * @param nums: a list of integer
 * @param k: an integer
 * @return: return an integer, denote the minimum length of continuous subarrays whose sum equals to k
 */
func SubarraySumEqualsKII(nums []int, k int) int {
	//map: k: 前缀和， v:该前缀和由前面多少个数组成
	mymap := map[int]int{}
	n := len(nums)
	ans := n + 1
	mymap[0] = 0 //很重要，关键
	sum := 0
	diff := 0
	for i := 0; i < n; i++ {
		sum += nums[i]
		diff = sum - k

		pos, ok := mymap[diff]
		if ok {
			cur := i - pos + 1
			if cur < ans {
				ans = cur
			}
		}

		mymap[sum] = i + 1
	}

	if ans == n+1 {
		return -1
	} else {
		return ans
	}
}

func main() {
	fmt.Println(SubarraySumEqualsKII([]int{1, 1, 1, 2}, 3))
	fmt.Println(SubarraySumEqualsKII([]int{2, 1, -1, 4, 2, -3}, 3))
	fmt.Println(SubarraySumEqualsKII([]int{1, 2}, 3))
}

/*
[1,2]
3
输出数据
-1
期望答案
2
提示
*/

/*
LintCode-Logo
学习
刷题
题集
群组
内推
VIP
CAT
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
1844 · 子数组和为K II
算法
中等
通过率
47%
题目
题解24
笔记51
讨论3
排名
记录
描述
给定一个整数数组和一个整数k，你需要找到和为k的最短非空子数组，并返回它的长度。

如果没有这样的子数组，返回-1.

数组中的元素可能小于0

样例
样例1：

输入:
nums = [1,1,1,2] and k = 3
输出:
2
样例2：

输入:
nums = [2,1,-1,4,2,-3] and k = 3
输出:
2
标签
推荐课程

系统设计 System Design 2022版
数据库、API、GFS、视频流等16大系统设计详解，实战练习拿下面试/晋升“拦路虎”
1343/3007
已开启智能提示
发起考试
30 分 00 秒
12345678910
public class Solution {
    /**
     * @param nums: a list of integer
     * @param k: an integer
     * @return: return an integer, denote the minimum length of continuous subarrays whose sum equals to k
*/
/*
public int subarraySumEqualsKII(int[] nums, int k) {
    // write your code here
}
}
控制台
        历史提交
        您有309条未读消息，请及时查看

*/
